17.1 準並行コピー方式：Bakerのアルゴリズム

GCサイクルの始めに世界を停止させて、ミューテータルートが直接指しているオブジェクトのコピーだけを行う。("準"並行)

この時点で、ミューテータは全て黒色になり、ミューテータの指しているオブジェクトは全てto空間にある

コレクタのコピーに加えて、to空間にあるオブジェクトのうち、灰色なもの(from空間へのポインタを持っている)のread時にfrom空間へのポインタをto空間へ張り替える(もしまだ未コピーならfromからtoへコピーもする)

e.g. collectもReadもCopyをする

『コレクタによる灰色オブジェクト1個の走査』と『ミューテータによるリードバリア』をatomicに行うことで、走査中のオブジェクトに対するミューテータのロードを防ぐ

同期粒度は粗い(オブジェクトレベル)

オブジェクトレベルでatomicにすることで以下が保証される

ミューテータが(たとえばwrite時に)ソースとターゲットの両方の正しい状態を見ている

ミューテータによるコピーとコレクタによるコピーが干渉しない

(アルゴリズム4-2(p57)がベースになっている)

code:17-1.py

# to空間のオブジェクトで、且つまだfrom空間へのポインタのみを指しているものが入っている。

# (worklistは灰色オブジェクトの集合)

shared worklist ← empty

def collect():

atomic

for each fld in Roots

process(fld) # ミューテータルートからすぐ辿れるオブジェクトを全て灰色にする

loop

if isEmpty(worklist)

break /* ループから抜ける*/

ref ← remove(worklist)

scan(ref)

def flip():

fromspace, tospace ← tospace, fromspace

free, top ← tospace, tospace + extent

# freeからtopまでの空間が使用可能。(freeがだんだん下がっていく)

def scan(toRef):

for each fld in Pointers(toRef)

process(fld)

def process(fld):

fromRef ← *fld

if fromRef ≠ null

*fld ← forward(fromRef) /* to 空間への参照で置き換える*/

# ポインタfromRefのto空間におけるアドレスを返す。

# fromRefの指すオブジェクトがまだto空間にコピーされていなければ、

# 実際にコピーを行い、

# forwardingAddress 関数の実装は省略されている

def forward(fromRef):

toRef ← forwardingAddress(fromRef)

if toRef = null /* 未コピー（未マーク） */

toRef ← copy(fromRef)

return toRef

# fromRefが指しているfrom空間のオブジェクトのコピーを行う。

def copy(fromRef):

toRef ← free

free ← free + size(fromRef)

if free > top

error "Out of memory"

move(fromRef, toRef)

# fromRefが指しているオブジェクトをtoRefの位置にコピーする

# この時点で、toRefの指すオブジェクトはto空間にあるが、

# 各フィールドはfrom空間を指している。

forwardingAddress(fromRef) ← toRef /* マークする*/

add(worklist, toRef)

return toRef

def atomic Read(src, i):

if isGrey(src)

ref ← forward(ref)

return ref

より粒度を上げるためworklistにフィールドへの参照を保持する手法がある。

灰色フィールドと黒色フィールドを区別したい(オブジェクトなら、灰色ビットをセットする場所があるが、フィールドには通常はセットする場所がない)

Cheney 式の走査(4-1(p57)のなんかうまいことやるやつ)を行うと、走査ポインタとの相対位置でフィールドが灰色かどうかを判定することができる。詳しくは19章(リアルタイムGC)で。

準並行準コピーGC(一部のオブジェクトをピン止めしてコピーしないやつ)

曖昧なルート(ポインタを保守的に取り扱う)から参照されるオブジェクトをピン止めする必要がある

Modula-2+やModula-3という言語で用いられた

仮想記憶のページ保護を用いて実装したので粒度が粗かった

C++で実験されたこともある

Hoskingによってオブジェクト単位でのリードバリアが(コンパイラを利用して)準並行準コピーに導入された